package sort.leetcode;

import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

/**
 * 215. 数组中的第K个最大元素
 * @author haomin
 * @date 2022/03/22 19:21
 **/
public class Num215_findtKhLargest {
    private static final ThreadLocalRandom random = ThreadLocalRandom.current();

    public  int findtKhLargest(int[] nums, int k) {
        quickSortInternal(nums,0,nums.length - 1);
        return nums[nums.length - k];
    }

    private  void quickSortInternal(int[] nums, int l, int r) {

        if(r - l <= 0){
            return;
        }
        int p = partition(nums,l,r);

        quickSortInternal(nums,l,p - 1);
        quickSortInternal(nums,p + 1,r);
    }

    private  int partition(int[] nums, int l, int r) {
        //不能使用 int random = new Random().nextInt(nums.length);
        int randomIndex = random.nextInt(l,r) ;
        int v = nums[l];

        int j = l;
        for (int i = l + 1; i <= r ; i++) {
            if(nums[i] < v){
                swap(nums,i,j + 1);
                j++;
            }
        }
        swap(nums,l,j);
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] =temp;
    }
}